/*
	平衡二叉排序树:
	1.左右子树深度之差绝对值不大于1的排序二叉树
	2.其左右子树也是平衡二叉树

	查找的平均复杂度O(log2n)
*/

#include <stido.h>
typedef int ElemType;

typedef struct blanode
{
	int key;
	int Bfactor;//平衡因子域
	ElemType data
	struct blanode *Lchild,*Rchild;
}BSTNode;

void InsertBST(BSTNode *T, BSTNode *S)
{
	BSTNode *f,*a,*b,*p,*q;
	if (T == NULL)
	{
		T = S;
		T -> Bfactor = 1;
		return;
	}

	a = p = T;
	/*a指向离s最近且平衡因子不为0的结点*/
	f = q = NULL;
	/*f指向a的父结点,q指向p的父结点*/
	while(p != NULL)
	{
		if (S -> key == p -> key)
			return;
		/*结点已存在返回*/
		if (p -> Bfactor != 0)
		{
			a = p;
			f = q;
		}

		q = p;

		if (S -> key < p -> key)
			p = p -> Lchild;
		else
			p = p -> Rchild;
	}
}